This chapter summarizes the foundations of Database Design Theory. This summary is similarly structured as in \cite{1992mannila,1995databases,2006arenas2}. Section~\ref{sec:relPre} gives a short introduction to the relational model. Then, Section~\ref{sec:relDep} introduces one type of data dependencies for the relational model, called functional dependencies. Finally, Section~\ref{sec:relNF} introduces the two most prominent normal forms for the relational model, Third Normal Form and Boyce-Codd Normal Form.


\begin{section}{Preliminaries}
\label{sec:relPre}
Codd introduced in \cite{1970codd} the relational model which is used by most database management systems (DBMS) today. Such a DBMS stores data in relations (or tables). Figure~\ref{fig:relCourse} shows an example relation storing information about courses of universities. A tuple (or row) of \textit{course} stores a lecture, its type and the room together with the rooms' location. \\

\begin{figure}[t]
\centering
\begin{tabular}{|l|l|l|l|}
\hline \multicolumn{1}{|c|}{$lecture$} & \multicolumn{1}{c|}{$type$} & \multicolumn{1}{c|}{$room$} & \multicolumn{1}{c|}{$building$} \\
\hline \hline Algebra I & VO & HS1 & Main \\
\hline Algebra I & UE & SEM1 & Dep \\
\hline Economics I & UE & SEM1 &  Dep \\ \hline
\end{tabular}
\caption{Relation $course$}
\label{fig:relCourse}
\end{figure}

\noindent As we have seen, each relation consists of two parts: the actual data, which varies over time, and the part considered to be fixed, the \textit{relational schema}. A schema, denoted as $R[U]$, consists of a \textit{schema name} ($R$) and a set of \textit{attributes} $U = \{ A_1, \ldots, A_n \}$. The values stored in each attribute $A \in U$ are of a particular \textit{domain} denoted as $Dom(A)$. We assume the domains to be infinite. The schema shown in Figure~\ref{fig:relCourse} is $course[U]$, where $U = \{ lecture, type, room, building \}$ and $Dom(lecture) = \Sigma^*$, i.e. the set of all strings. A \textit{tuple} is a function with domain $U$ that assigns to each attribute of a relation a value of the domain. An \textit{instance} $I$ of a relation consists of a set of tuples. For example, the instance depicted in Figure~\ref{fig:relCourse} is $I(course) = \{ t_1, t_2, t_3 \}$, where $t_1(lecture) = \mbox{``Algebra I''}$, and so on. Let $X \subseteq U$, we denote with $t[X]$ the tuple restricted to the attributes in $X$. Given a set of tuples $T$, e.g. $I(course)$, we denote with $T[X]$, the set of tuples restricted to the attributes in $X$. A \textit{database schema} $\bm{S}$ consists of several relational schemas, i.e. $\bm{S} = \{ R_1[U_1], \ldots R_n[U_n] \}$. Additionally, constraints might be imposed over a relational schema. Such constraints restrict the possible relational schema instances. For example, the instance in Figure~\ref{fig:relCourse} depicts that one room is associated to a building. In order to express such constraints, we need to add \textit{data dependencies} to a relational schema. Different classes of data dependencies will be considered in Section~\ref{sec:relDep}. A relational schema $R[U]$ together with some set of dependencies $\Sigma$, denoted by $(R[U],\Sigma)$, is, for the sake of simplicity, also called relational schema \cite{2006arenas2}. We denote by $\ffo{Inst}\left(R\left[U\right]\right)$ the set of all possible instances of the relational schema $R\left[U\right]$.
\end{section}

\begin{section}{Data Dependencies}
\label{sec:relDep}
Data dependencies impose constraints over an instance of a relational schema. Let us first introduce two concepts common to all classes of data dependencies, \textit{dependency implication} and \textit{dependency inference}. Let $\varphi$ denote a dependency and $\Sigma$ a set of dependencies. A set of dependencies $\Sigma$ implies a dependency $\varphi$, denoted by $\Sigma \models \varphi$, if for every database instance $I$ that satisfies all constraints in $\Sigma$, it is the case that $I$ satisfies $\varphi$. The set of all dependencies implied by $\Sigma$ is denoted by $\Sigma^+$. Dependency implication can be decided using different methods. On the one hand, there are algorithms, on the other hand we can try to construct a proof for the implication of a FD by using an inference system. Such an inference system consists of a set of inference rules $\mcI$. Let $\mcC$ be a class of dependencies, e.g. the class of Functional Dependencies. We say a set of rules $\mcI$ is \textit{complete} for a class of dependencies $\mcC$, if for every set $\Sigma \cup \{ \varphi \}$, if $\Sigma \models \varphi$, then $\Sigma \vd_\mcI \varphi$, i.e. $\varphi$ is provable from $\Sigma$ using $\mcI$. Furthermore, $\mcI$ is \textit{sound} for $\mcC$ if $\Sigma \vd_\mcI \varphi$ implies $\Sigma \models \varphi$. The three most important classes of dependencies are Functional Dependencies, Multi-Valued Dependencies and Join Dependencies. Boyce-Codd Normal Form uses Functional Dependencies. Since in this work we primarily focus on BCNF, we only introduce Functional Dependencies here. We exhibit the implication problem for Functional Dependencies and establish a set of sound and complete inference rules.

\begin{subsection}{Functional Dependencies}
\label{ssec:rel_fd}
Functional Dependencies (FDs) are the most important class of dependencies in schema design. Key dependencies, a special type of FDs, are supported by most DBMS today. Let $U$ be a set of attributes, and let $X,Y \subseteq U$. A \textit{Functional Dependency} over $U$ is an expression of the form $X \ra Y$. If $Y = U$ then $X \ra Y$ is called a \textit{key dependency}. An FD is called \textit{trivial} if $Y \subseteq X$. An instance $I$ of $R[U]$ satisfies an FD $X \ra Y$, denoted by $I \models X \ra Y$, if for every pair of tuples $t_1$, $t_2$ in $I$, whenever $t_1[X] = t_2[X]$, then $t_1[Y] = t_2[Y]$. Intuitively, an FD says that if two tuples agree on the values of $X$ they must also agree on the values of $Y$.  \\

\noindent Now consider the relation $course$ in Figure~\ref{fig:relCourse}. We already noted that each room is associated to a building. Therefore, $room \ra building$ is an FD over the relation $course$. Additionally, a lecture together with its type determines the room they can be held in. Also, rooms can only serve lectures of a particular type. Therefore the set of FDs $\Sigma_{course}$ over the relation $course$ is:

\begin{align}
   room &\ra building \label{eqn:fd_c1} \\
   lecture, type &\ra room \label{eqn:fd_c2} \\
   room &\ra type \label{eqn:fd_c3} 
\end{align}

\noindent We have now specified the relational schema $(course[U],\Sigma_{course})$, with \linebreak $U = \{ lecture, type, room, building \}$. Notice, that the relation in Figure~\ref{fig:relCourse} is a valid instance of this schema.

\begin{subsubsection}{Implication of FDs}
\label{sssec:fd_impl}
The implication of a particular FD $\varphi$ by a set of FDs $\Sigma$ can be determined by computing the closure of a set of attributes $X$. Let $X \subseteq U$ be a set of attributes. The \textit{closure} of $X$, denoted by $X^+$, are all attributes implied by $X$, i.e. $X^+ = \{ A \mid \Sigma \models X \ra A \wedge A \in U \}$. A naive algorithm computes $X^+$ in $O(n^2)$, where $n$ is the length of $\Sigma$ and $X$. Algorithm~\ref{alg:beeri} developed by Beeri and Bernstein \cite{1979beeribernstein, 1979bernstein} computes $X^+$ in linear time. We can now check if an FD $\varphi = X \ra Y$ is implied by a set of FDs $\Sigma$, since $\Sigma \models X \ra Y$ if and only if $Y \subseteq X^+$. Therefore, implication of FDs can be decided in linear time. \\

\begin{algorithm}[t]
\SetKwInOut{Input}{input}
\SetKwInOut{Output}{output}

\Input{A set $U$ of attributes, a set $\Sigma$ of functional dependencies over $U$, and a set $X \subseteq U$.}
\Output{The closure $X^+$ of $X$ with respect to $\Sigma$}

\BlankLine

\emph{unmark all members of $X$}\;
\ForEach{$\varphi = Y \ra Z \in \Sigma$}{
   $count(\varphi) \la |Y|$\;
   \ForEach{$A \in Y$}{
      add $\varphi$ to the list $L(A)$\;
   }
}
$CL \la X$\;
\While{CL contains an unmarked element $A$}{
   mark $A$\;
   \ForEach{$\varphi \in L(A)$}{
      $count(\varphi) \la count(\varphi) - 1$\;
      \If{$count(\varphi) = 0$}{
         let $\varphi = Y \ra Z$\;
         $CL \la CL \cup Z$\;
      }
   }
}
\BlankLine
\caption{Linear time algorithm to compute the closure $X^+$ of a set of attributes $X$ (from \cite{1992mannila})}\label{alg:beeri}
\end{algorithm}

\noindent As an example, consider the FDs $\Sigma_{course}$ and the FD $\varphi_{course} = lecture, type \ra building$. We want to check if $\Sigma_{course} \models \varphi_{course}$. First, we use Algorithm~\ref{alg:beeri} to compute $\{lecture, type\}^+ = \{lecture, type, room, building\}$. Then $\varphi_{course}$ is implied by the FD $\Sigma_{course}$, since $building \in \{lecture, type\}^+$.
\end{subsubsection}

\begin{subsubsection}{Axiomatization for FDs}
\label{sssec:fd_axiom}
An alternative to the implication problem is to provide a proof for an FD. Such a proof is constructed using inference rules. Armstrong introduced in \cite{1974armstrong} the following sound and complete set of inference rules, also called Armstrong Axioms:
\begin{align}
   & \mbox{FD1 (Reflexivity):} & \mbox{If } Y \subseteq X \mbox{, } &\mbox{then } X \ra Y \\ 
   & \mbox{FD2 (Augmentation):} & \mbox{If } X \ra Y \mbox{, } &\mbox{then } XZ \ra YZ \\
   & \mbox{FD3 (Transitivity):} & \mbox{If } X \ra Y \mbox{ and } Y \ra Z \mbox{, } &\mbox{then } X \ra Z
\end{align}
\noindent For example, $\varphi_{course}$ can be inferred by applying transitivity (FD3) to $lecture, type \ra room$ and $room \ra building$. 
\end{subsubsection}

\end{subsection}

\end{section}

\begin{section}{Normal Forms}
\label{sec:relNF}
Normal forms are one of database theory most important contributions to schema design. The goal of normal forms is to formulate criteria for ``good'' relational schemas. Intuitively, such ``good'' schemas should help to avoid redundant information, and update, insertion and deletion anomalies. \\

\noindent Before we define normal forms, we need some auxiliary definitions. Let $\left( R\left[U\right],\Sigma \right)$ be a relational schema with the functional dependencies $\Sigma$. We call $X\subseteq U$ a \textit{superkey} if $\Sigma \models X \ra U$. A \textit{key} is a minimal superkey. The attributes $A$ in $X$, where $X$ is a key of $R$, are called \textit{key attributes} \cite{1995databases}. \\

\noindent We only study Third Normal Form (3NF) and Boyce-Codd Normal Form (BCNF) here. For completeness, First Normal Form (1NF) states that attributes in relations are atomic \cite{1992mannila}, which is an assumption already made by the relational model. Second Normal Form (2NF) demands that all non-key attributes should depend on the whole key of a relation \cite{1992mannila}. All normal forms require the relation to be in the weaker normal form, i.e. 3NF requires that the relation is in 2NF and 1NF.

\begin{subsection}{Third Normal Form}
Third Normal Form was first proposed in \cite{1971codd, 1971codd2} in order to avoid update anomalies.

\begin{definition}{(Third Normal Form \cite{1982zaniolo,1995databases})}
\label{def:3NF}
Let $\left( R\left[U\right],\Sigma \right)$ be a relational schema, where $\Sigma$ is a set of functional dependencies. $\left( R\left[U\right],\Sigma \right)$ is in \textit{third normal form (3NF)} if whenever $X \ra A$ is a nontrivial FD implied by $\Sigma$, then $X$ is a superkey or $A$ is a key attribute.
\end{definition}

\noindent In other words, Definition~\ref{def:3NF} states that whenever an attribute $A$ is functionally dependent on another set of attributes $X$, then $X$ is a superkey or $A$ is part of the key of $R$. We will now illustrate 3NF with the following example.

\begin{example}
\label{ex:3NF}
Consider the relational schema $(course[U],\Sigma_{courses})$ introduced in Section~\ref{sec:relPre} and extended with FDs in Section~\ref{sec:relDep}. Now consider the FD $room \ra building$. Neither $room$ is a superkey, since $room \ra lecture$ is not a valid FD in the relational schema, nor $building$ is part of the key of $R$, which is $lecture, type, room$. Therefore, this schema is not in 3NF. We can split the relation $course$ into a relation $course$ with attributes $lecture$, $type$, and $room$ and into a relation $rooms$ with attributes $room$ and $building$. Notice, that this new set of relations $course$ and $room$ is in 3NF.
\end{example}


\end{subsection}


\begin{subsection}{Boyce-Codd Normal Form}
Boyce-Codd Normal Form (BCNF) was introduced in \cite{1974codd} and can be summarized with ``Do Not Represent the Same Fact Twice'' \cite{1995databases}, which eliminates redundancies and update anomalies. BCNF is defined as follows:

\begin{definition}{(Boyce-Codd Normal Form \cite{1995databases}}
Let $\left( R\left[U\right],\Sigma \right)$ be a relational schema, where $\Sigma$ is a set of functional dependencies. $(R[U],\Sigma)$ is in \textit{Boyce-Codd normal form} (BCNF) if $\Sigma \models X\ra U$ whenever $X \ra Y$ is a nontrivial FD implied by $\Sigma$. A database schema $(\textbf{R}, \Sigma)$ is in BCNF if each of its relation schemas is.
\end{definition}

\noindent Put differently, a schema is in BCNF if for every nontrivial functional dependency $X \ra A \in \Sigma^+$, $X$ is a superkey \cite{1992mannila}. Thus, compared to 3NF, BCNF drops the condition that $A$ might be part of the key. The algorithm for testing BCNF works as follows: For every FD $X \ra Y \in \Sigma$, we compute $X^+$ using Algorithm~\ref{alg:beeri}. If $X^+ = U$ then we continue with the next FD. Since Algorithm~\ref{alg:beeri} runs in linear time, we can decide if a relational schema is in BCNF in quadratic time. Example~\ref{ex:3NF} shows a relational schema that is in 3NF. Next, we show that this relational schema is not in BCNF:

\begin{example}
\label{ex:BCNF}
Let $course(lecture,type,room)$ be the relational schema obtained after decomposition into 3NF. The FDs for the relational schema $course$ are \\ $(lecture,type \ra room)$ and $(room \ra type)$. This schema is not in BCNF since $room \ra lecture$ is not implied by the above FDs. An instance of this schema is presented in Figure~\ref{fig:relCourse3NF}. Let us explain at this example the BCNF intuition ``Do Not Represent the Same Fact Twice''. We extract the columns used in the FD that leads to the violation of BCNF. Those are $room$ and $type$. The instance in Figure~\ref{fig:relCourse3NF} restricted to $room$ and $type$ consists of three rows, where two rows appear twice (those are $\left(\mathit{UE}, \mathit{SEM1}\right)$). Since the instance in Figure~\ref{fig:relCourse3NF} is a valid instance we have stored \textit{twice} the information that in the room SEM1 courses of the type UE can be taught. \end{example}

\begin{figure}[t]
\begin{center}
\begin{tabular}{|l|l|l|}
\hline \multicolumn{1}{|c|}{$lecture$} & \multicolumn{1}{c|}{$type$} & \multicolumn{1}{c|}{$room$} \\
\hline \hline Algebra I & VO & HS1  \\
\hline Algebra I & UE & SEM1 \\
\hline Economics I & UE & SEM1 \\ \hline
\end{tabular}
\end{center}
\caption{Relation $course$ in 3NF}
\label{fig:relCourse3NF}
\end{figure}

\noindent Relational schemas that are not in BCNF can be repaired. We call such a repair algorithm a \textit{decomposition}. The basic idea of a BCNF decomposition algorithm is, to find a FD $X \ra Y$ which leads to a BCNF violation. Notice that $Y$ have to be all attributes implied by $X$. We then create a new relation for the attributes $X$ and $Y$ and remove the attributes $Y$ from the original relation. Therefore, we have repaired the BCNF violation, that has originated from the FD $X \ra Y$. Such a decomposition should preserve data and dependencies. The BCNF decomposition algorithm preserves the data, but, unfortunately, is not dependency preserving (see Theorem 11.2.8 of \cite{1995databases}). The next example illustrates the loss of a dependency due to the BCNF decomposition algorithm.

\begin{figure}[b]
\begin{center}
\begin{tabular}{|l|l|c|l|l|}
\multicolumn{2}{c}{$course$} & \multicolumn{1}{c}{} & \multicolumn{2}{c}{$rooms$} \\
\cline{1-2} \cline{4-5} \multicolumn{1}{|c|}{$lecture$} & \multicolumn{1}{c|}{$room$} & & \multicolumn{1}{c|}{$room$} & \multicolumn{1}{c|}{$type$} \\
\cline{1-2} \cline{4-5} \cline{1-2} \cline{4-5} Algebra I & HS1 & &  HS1 & VO  \\
\cline{1-2} \cline{4-5} Algebra I & SEM1 & & SEM1  & UE\\
\cline{1-2} \cline{4-5} Economics I & SEM1 \\ \cline{1-2} 
\end{tabular}
\end{center}
\caption{Relation $course$ and $rooms$ in BCNF}
\label{fig:relCourseBCNF}
\end{figure}

\begin{example}
Consider the relational schema and instance given in Figure~\ref{fig:relCourse3NF} of Example~\ref{ex:BCNF}. Since the FD $room \ra type$ leads to a BCNF violation, we create a new relation $rooms$ with the attributes $room$ and $type$. We remove the attribute $type$ from the relation $course$. Additionally, we need to drop the FD $lecture,type \ra room$, since $type$ does not belong to the relation $course$ anymore. Therefore, the algorithm does not preserve the FD $lecture,type \ra room$. The result is the database schema in BCNF consisting of the relations:
\begin{align*}
   (course(lecture, room),\emptyset) & & (rooms(room, type),\{ room \ra type \})
\end{align*}
\noindent The resulting database instance with the same information as in Figure~\ref{fig:relCourse3NF} is given in Figure~\ref{fig:relCourseBCNF}. Unfortunately, there is no BCNF decomposition of $course$ that preserves dependencies.
\end{example}
\end{subsection}

\end{section}

\begin{section}{Summary}
 In this chapter we have introduced the relational model as a formal model of relational databases. Then, we established functional dependencies as a formalism for data dependencies over a relational schema. We have investigated the implication problem for FDs. The presented algorithm decides the implication problem for FDs in linear time. Additionally, we can use Armstrong Axioms to prove the implication of FDs. \\
 
 \noindent Then, we introduced two different normal forms for the relational model. A relational schema $R$ is in Third Normal Form if for every attribute $A$ that is functionally dependent on some other attributes $X$, then $X$ is a superkey or $A$ is a key attribute. This normal form avoids update anomalies. Boyce-Codd Normal Form eliminates redundancies and update anomalies. BCNF drops the condition that $A$ might be a key attribute. Therefore, BCNF is more restrictive than 3NF. If a relational schema is in BCNF can be checked in quadratic time. Clearly, every schema that is in BCNF is also in 3NF. At the end of this chapter we have showed that we can repair relational schemas that are not in BCNF, such that the resulting relational schema is in BCNF.
\end{section}

